package com.leetcode.partition7;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/11 8:37
 */
public class LC698划分为K个相等的子集 {

    public static boolean canPartitionKSubsets(int[] nums, int k) {
        if (k == 1) return true;
        int sum = 0, target;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
        if (sum % k != 0) return false;
        target = sum / k;
        Arrays.sort(nums);
        int[] bucket = new int[k];          //存放子集和，总共有k个，相当于有k个桶，需要用nums中的数据将其填满
        return backtracking(target, nums, bucket, nums.length - 1);
    }

    public static void main(String[] args) {
//        int[] nums = {2, 2, 2, 2, 3, 4, 5};
//        int k = 3;
//        int[] nums = {4, 3, 2, 3, 5, 2, 1};
//        int k = 4;
        int[] nums = {1, 1, 1, 1, 2, 2, 2, 2};
        int k = 4;
        System.out.println(canPartitionKSubsets(nums, k));
    }

//    private static List<Integer> memoization(Map<Integer, List<Integer>> memo, int[] nums, boolean[] visited, final int target, int sum, int startIndex) {
//        if (startIndex == nums.length || sum != target) return null;
//
//        if (memo.containsKey(startIndex)) return memo.get(startIndex);
//        List<Integer> ans = new ArrayList<>();
//        for (int i = startIndex; i < nums.length; i++) {
//            if (visited[i]) continue;
//            visited[i] = true;              //标记为已访问
//            sum += nums[i];
//            List<Integer> res = memoization(memo, nums, visited, target, sum, i + 1);
//            if (res == null) {              //没有符合条件的解，进行回溯
//                visited[i] = false;
//                sum -= nums[i];
//                continue;
//            }
//            ans.addAll(res);
//            memo.put(startIndex, new ArrayList<>(ans));
//        }
//        return memo.get(startIndex);
//    }

    private static boolean backtracking(int target, final int[] nums, final int[] bucket, int index) {
        if (index < 0) return true;       //从后往前遍历，如果当前的索引遍历到了-1，说明nums后面的所有数字都已成功放入
        for (int i = 0; i < bucket.length; i++) {       //遍历桶，尝试把每一个桶都刚好装满
            //两种情况，当前桶正好被装满，或者当前数放入后还能放入其它数
            if (bucket[i] + nums[index] == target || (target - (bucket[i] + nums[index])) >= nums[0]) {
                bucket[i] += nums[index];       //将当前数字放入桶中
                if (backtracking(target, nums, bucket, index - 1)) return true;     //当前方案可行，不需要回溯
                bucket[i] -= nums[index];       //回溯，当前数字放入后不能满足要求，取出当前数字
            }
        }
        return false;
    }
}
